package com.wk.arth.dp;

import java.util.HashMap;
import java.util.Map;

public class SubArray {

	/**
	 * 同余法   (rem+n*k)%k = rem
	 *  在i处余数和j处余数相同,则从i+1到j的和是k的整数倍
	 *  子数组长度至少为2
	 *  k=0,子数组和也必须为0
	 * @param nums
	 * @param k
	 * @return
	 */
    public boolean checkSubarraySum(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        int sum = 0;
        map.put(0, -1);
        for (int i = 0; i < nums.length; i++) {
			sum+=nums[i];
			if(k!=0) {
				sum = sum%k;
			}
			if(map.containsKey(sum)) {
				if(i-map.get(sum)>1) {
					return true;
				}
				
			}else {
				map.put(sum, i);
			}
			
		}
        return false;
    }
	public static void main(String[] args) {
//		int[] nums = {23,2,4,6,7};
//		int k = -6;
		int[] nums = {12,0};//{12,0}
		int k = 0;
		boolean checkSubarraySum = new SubArray().checkSubarraySum(nums, k);
		System.out.println(checkSubarraySum);
		System.out.println(0%12);
	}
}
